/*
 * @Author: 缄默
 * @Date: 2021-11-15 20:33:18
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-15 21:03:13
 */

//统计完全二叉树的节点个数

//遍历整棵树即可得到结果 但是不是最优解 最优解可在O(h2)内实现

#include "../../DataStructure/tree.hpp"

int getTreeHigh(const TreeNode* head);
int getTreeNodeNum(const TreeNode* head);

int main() {
    vector<int> preOrder({4, 2, 1, 0, 3, 6, 5, 7});
    vector<int> inOrder({0, 1, 2, 3, 4, 5, 6, 7});
    TreeNode* head = buildTree(preOrder, inOrder, 0, 0, preOrder.size() - 1);
    cout << getTreeHigh(head) << endl;
    cout << getTreeNodeNum(head) << endl;
}

int getTreeNodeNum(const TreeNode* head) {
    if (head == nullptr) return 0;
    int h = getTreeHigh(head);
    int rightHigh = getTreeHigh(head->right);
    if (h - 1 == rightHigh) {
        //左移运算
        return getTreeNodeNum(head->right) + (1 << (h - 1));
    }
    else {
        return getTreeNodeNum(head->left) + (1 << (h - 1 - 1));
    }

}

int getTreeHigh(const TreeNode* head) {
    int high = 0;
    while (head != nullptr) {
        high++;
        head = head->left;
    }
    return high;
}
